/*
The MIT License (MIT)

Copyright (c) 2013 Mike Dapiran, Brian May, Richard Pospesel, and Bert Wierenga

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#pragma once

#include "hhdVector.hpp"

namespace hhd
{
    static unsigned int _counter = 0;

    /**
    * This class is a Node for the following MinHeap Class. It keeps track of extra information
    * namely the position it is at in the heap for constant time lookup in the heap.
    */
    template<typename T> class MinHeapNode
    {
    public:
        MinHeapNode()
			: _index_in_heap(0)
        {
            _id = _counter++;
        }

        ~MinHeapNode()
        {
        };

        MinHeapNode(const T& item) : _index_in_heap(0)
        {
            _object = item;
        }

        MinHeapNode(const MinHeapNode& source)
        {
            _index_in_heap = source._index_in_heap;
            _object = source._object;
            _id = source._id;
        }

        MinHeapNode& operator=(const MinHeapNode& source)
        {
            _index_in_heap = source._index_in_heap;
            _object = source._object;
            _id = source._id;
            return *this;
        }

        bool operator==(const MinHeapNode& other)
        {
            if(_id == other._id)
            {
                return true;
            }

            return false;
        }

        int _index_in_heap;
        T _object;

    protected:
        unsigned int _id;
    };

    /**
    * This class implements a priority queue in the form of a heap, specifically one that
    * will maintain the heap data structure favoring smaller values determine by operator<
    * towards the beginning of the queue.
    *
    * @author Bert Wierenga
    */
    template<typename NodeType> class MinHeap
    {
    public:
        MinHeap()
            : _size(0)
        {
        }

        ~MinHeap()
        {
        }

        int size()
        {
            return _size;
        }

        bool isEmpty()
        {
            return _size == 0 ? true : false;
        }

        void clear()
        {
            for( int i = 1 ; i <= _size; i++)
            {
                _data[i]->_index_in_heap = 0;
            }

            _size = 0;
        }

        /*
        * Called to add an item to the MinHeap
        *
        * @return Returns a reference to the newly stored node.
        */
        NodeType* insert(NodeType* item)
        {
            //make sure there is enough room to insert it
            _size++;
            while( _data.size() < _size+2)
            {
                _data.add( NULL );
            }

            //place it
            int i = _size;

            //compare the parents object against this new item.
            //make sure we don't go past the front of the heap.
            while( i > 1 && _data[ parentIndex(i) ]->_object > item->_object )
            {
                //do the move
                _data[i] = _data[ parentIndex(i) ];
                //update index
                _data[i]->_index_in_heap = i;

                //increment
                i = parentIndex( i );
            }
            //set the new ones object and index
            _data[i] = item;
            _data[i]->_index_in_heap = i;

            return _data[i];
        }

        /*
        * Called to update the position of a node in the heap, behavior is undetermined
        * if the passed node is not already a node in the heap.
        *
        * @param node The node to update priority on
        *
        * @return Returns a reference to the passed in node as it is currently stored in the heap.
        */
        NodeType* updatePriority(NodeType* node )
        {
            if( node->_index_in_heap > _size )
            {
                error("Index past bounds of heap");
            }

            //compare the parents object against this node's object.
            //make sure we don't go past the front of the heap.

            int parent_index;
            int child_index;

            while( (child_index = node->_index_in_heap) > 1 &&
                    _data[ parent_index = parentIndex( node->_index_in_heap ) ]->_object > node->_object )
            {
                //do the move
                _data[ child_index ] = _data[ parent_index ];
                //update the indecies
                _data[ child_index ]->_index_in_heap = child_index;
                node->_index_in_heap = parent_index;
            }
            //set it
            _data[ node->_index_in_heap ] = node;

            return _data[ node->_index_in_heap ];
        }

        /*
        * Removes and returns the Node of highest priority
        */
        NodeType* extractMin()
        {
            if( _size == 0 )
            {
                error("Attempting to remove from an empty heap");
                return 0;
            }
            //save it off
            NodeType* result = _data[1];
            result->_index_in_heap = 0;

            //fix heap
            _data[1] = _data[_size];
            _size--;
            Heapify(1);

            //return it
            return result;
        }

    private:
        //actual memory storage
        Vector<NodeType*> _data;

        //true size
        int _size;

        /*
        * Maintains the correct ordering in the heap after a value is removed at
        * a given index in the heap.
        */
        void Heapify(int i)
        {
            int l = leftChildIndex(i);
            int r = rightChildIndex(i);

            int smallestsIndex;

            //figure out which of the three (parent or either of its two children) is smallest
            if( l <= _size &&  _data[l]->_object < _data[i]->_object  )
            {
                smallestsIndex = l;
            }
            else
            {
                smallestsIndex = i;
            }

            if( r <= _size && _data[r]->_object < _data[smallestsIndex]->_object )
            {
                smallestsIndex = r;
            }

            //if its not the parent, do a swap, repeat
            if( smallestsIndex != i )
            {
                NodeType* temp_node = _data[i];

                _data[i] = _data[smallestsIndex];
                _data[i]->_index_in_heap = i;

                _data[smallestsIndex] = temp_node;
                _data[smallestsIndex]->_index_in_heap = smallestsIndex;
                Heapify( smallestsIndex );
            }
        }

        inline int leftChildIndex(int parent_index)
        {
            return parent_index << 1;
        }

        inline int rightChildIndex(int parent_index)
        {
            return (parent_index << 1) + 1;
        }

        inline int parentIndex(int child_index)
        {
            return child_index >> 1;
        }
    };
}
